import java.util.LinkedList;
import java.util.Queue;

/**
 * Creat with IntelliJ IDEA
 * Description
 * User: mamba24
 * Date: 2022-06-13
 * Time: 21:22
 * To BE A Better Person-2020-3-2
 */
class MyTreeNode{
  public static class Node{
       public char val;
       public Node leftchild;
       public Node rightchild;
       public Node(char val){
           this.val=val;
       }
   }

       public Node CreateTree(){
        Node A=new  Node('A');
        Node B=new  Node('B');
        Node C=new  Node('C');
        Node D=new  Node('D');
        Node E=new  Node('E');
        Node F=new  Node('F');
        Node G=new  Node('G');
        A.leftchild=B;
        A.rightchild=C;
        B.leftchild=D;
        B.rightchild=E;
        C.leftchild=F;
        C.rightchild=G;
        return A;
    }
    //前序遍历
    void preOrder(Node root)
    {
        if(root == null) return ;
        System.out.print(root.val+",");
        preOrder(root.leftchild);
        preOrder(root.rightchild);
    }
    // 中序遍历
    void inOrder(Node root)
    {
        if(root == null) return ;
        preOrder(root.leftchild);
        System.out.print(root.val+",");
        preOrder(root.rightchild);
    }
    // 后序遍历
    void postOrde(Node root)
    {
        if(root == null) return ;
        System.out.print(root.val+",");
        preOrder(root.leftchild);
        preOrder(root.rightchild);
    }
    public static int s;
    public void size(Node root){
        if(root == null) {
            return;
        }
        MyTreeNode.s++;
        size(root.leftchild);
        size(root.rightchild);
    }
//    public int size2(Node root){
//        if(root == null) return 0;
//        return size2(root.rightchild)+size2(root.leftchild)+1;
//    }
    // 获取叶子节点的个数
    public static int s2;//记录叶子节点的个数

    /**
     * 遍历的方法计算叶子节点的个数
     * @param root
     */
    public void getLeafNodeCount(Node root){
        if(root == null ) return;
        if(root.leftchild==null && root.rightchild==null) s2++;
        getLeafNodeCount(root.leftchild);
        getLeafNodeCount(root.rightchild);
    }

    /**
     * 用子问题的方法计算叶子节点的个数
     * @param root
     * @return
     */
//    public int getLeafNodeCount2(Node root) {
//        if(root.leftchild!=null&&root.rightchild!=null)
//            return getLeafNodeCount2(root.leftchild)+getLeafNodeCount2(root.rightchild);
//        return 1;
//    }

    public int getHigh(Node root) {
        if(root == null) return 0;
        int left=getHigh(root.leftchild);
        int right=getHigh(root.rightchild);
        return left>right?left+1:right+1;
    }
    // 检测值为value的元素是否存在
    Node find(Node root, char val){
        if(root == null) return null;
        if(root.val==val) return root;
        Node findNoderight=find(root.rightchild,val);
        Node findeNodeleft=find(root.leftchild,val);
        if(findeNodeleft==null){
            return findNoderight;
        }else {
            return findeNodeleft;
        }
    }
    void levelOrder(Node root) {
        if(root == null) return;
        Queue<Node> queue=new LinkedList<>();
        queue.offer(root);
    }

    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(Node root){
        if(root == null) return false;
        Queue<Node> queue=new LinkedList<>();
        queue.offer(root);

    }
}

public class TestDemo {
    public static void main(String[] args) {
        MyTreeNode myTreeNode=new MyTreeNode();
        MyTreeNode.Node root= myTreeNode.CreateTree();
        myTreeNode.preOrder(root);
        System.out.println();
        myTreeNode.inOrder(root);
        System.out.println();
        myTreeNode.preOrder(root);
        System.out.println();
        myTreeNode.size(root);
        myTreeNode.getLeafNodeCount(root);
        MyTreeNode.Node ret3=myTreeNode.find(root,'G');
        int ret= myTreeNode.size2(root);
        int ret2= myTreeNode.getLeafNodeCount2(root);
        System.out.println("the number of node is>:"+MyTreeNode.s);
        System.out.println("the number of node is>:"+ret);
        System.out.println("the number of leaf node is>:"+MyTreeNode.s2);
        System.out.println("the number of leaf node is>:"+ret2);
        System.out.println("the hight of tree is>:"+myTreeNode.getHigh(root));
        System.out.println(ret3.val);
    }

}
